package com.xucy.springboot.common.BinarySortedTree;

/**
 * @Author xucy
 * @Date 2019-04-18 10:02
 * @Description
 **/

public class Node {

    int value;
    Node leftNode;
    Node rightNode;

    public  Node(int value){
        this.value=value;
    }

    /**
     * 添加节点
     *
     * @Author xucy
     * @Date 10:48 2019-04-18
     * @param
     * @return
     */
    public  void addNode(Node node){
        Node newNode=node;

        if(value>node.value){
            if(this.leftNode!=null){
                newNode=this.leftNode;
                newNode.addNode(node);
            }else{
                this.leftNode=node;
            }

        }

        if(value<node.value){
            if(this.rightNode!=null){
                newNode=this.rightNode;
                newNode.addNode(node);
            }else{
                this.rightNode=node;
            }

        }
    }

    //中序遍历
    public static  void midSort(Node node){

        if(node.leftNode!=null){
            midSort(node.leftNode);
        }

        System.out.println(node.value);

        if(node.rightNode!=null){
            midSort(node.rightNode);
        }

    }

    /**
     * 查找节点
     *
     * @Author xucy
     * @Date 10:51 2019-04-18
     * @param
     * @return
     */
    public Node search(int val){

        if(this.value==val){
            return this;
        }else if(this.value<val){
            if(this.rightNode!=null){
                return  this.rightNode.search(val);
            }else{
                return null;
            }
        }else if(this.value>val){
            if(this.leftNode!=null){
                return this.leftNode.search(val);
            }else{
                return null;
            }
        }
        return null;
    }

    /**
     * 删除节点
     *
     * @Author xucy
     * @Date 10:49 2019-04-18
     * @param
     * @return
     */
    public  void deleteNode(int  val){
        Node searchNode=search(val);
        if(searchNode==null){
            return;
        }else{
            //找到他的父节点
            Node parent=searchParent(val);
            //删除的节点是叶子节点
            if(searchNode.leftNode==null&& searchNode.rightNode==null){
                if(parent.leftNode.value==val){
                    parent.leftNode=null;
                }else{
                    parent.rightNode=null;
                }
                //删除节点有两个子节点
            }else if(searchNode.rightNode!=null && searchNode.leftNode!=null){
                    //删除右子树中最小的节点，获取到该节点的值
                    int min =deleteMin(searchNode.rightNode);
                    searchNode.value=min;

            }else{
                //删除节点有一个节点，判断是有父节点的右节点 还是有左节点
                if(parent.leftNode.value==val){
                    //判断删除节点有左节点还是右节点
                    if(searchNode.leftNode!=null){
                        parent.leftNode=searchNode.leftNode;
                    }else{
                        parent.leftNode=searchNode.rightNode;
                    }
                }else{
                    if(searchNode.leftNode!=null){
                        parent.rightNode=searchNode.leftNode;
                    }else{
                        parent.rightNode=searchNode.rightNode;
                    }
                }

            }
        }
    }

    //删除右子树中最小的节点，获取到该节点的值
    private int deleteMin(Node node) {
        //找到最小的节点
        Node target=node;
        while (target.leftNode!=null){
            target=target.leftNode;
        }

        //删除最小节点，如果最小节点有右节点 ，则右节点不删除，上升到最小节点位置
        deleteNode(target.value);

        return target.value;
    }

    //找到他的父节点
    public Node searchParent(int val){
        if(leftNode.value==val||rightNode.value==val){
            return this;
        }else{
            if(value>val){
                return leftNode.searchParent(val);
            }else{
                return rightNode.searchParent(val);
            }
        }

    }
}
